λ¬Έμ
π Logic
private void dfs() {
Stack<Integer> stack = new Stack<>();
stack.push(0);
visited[0] = true;
for (int next : adjList.get(0)) stack.push(next);
while(!stack.empty()) {
int now = stack.pop();
if (visited[now]) continue;
// before μ 보λ₯Ό μ
λ°μ΄νΈνμ§ μλ λ°©λ€μ λͺ¨λ 0λ² λ°©μ΄ μ°μ λ°©λ¬Έλλ κ²½μ°
if (!visited[before[now]]) {
after[before[now]] = now;
continue;
}
visited[now] = true;
for (int next : adjList.get(now))
if (!visited[next]) stack.push(next);
stack.push(after[now]);
}
}
- Stackμ μ΄μ©ν DFSλ₯Ό μννλ€.
- 0λ² λ°©μμ κ° μ μλ λ°©λ€μ stackμ λ£λλ€.
-
λ°©λ¬Ένμ§ μμ λ°©μ λν΄,
- μ°μ λ°©λ¬Έν΄μΌ νλ λ°©μ λ°©λ¬Ένμ§ μμ κ²½μ°, μ΄ν λ°©λ¬Έν΄μΌ νλ λ°©λ€μ μ μ₯νλ
afterμ νμ¬ λ°©μ μ μ₯νλ€. - λ°©λ¬Έν κ²½μ°, νμ¬ λ°©μ λ°©λ¬Έ μ¬λΆλ₯Ό μ΅μ ννκ³ , νμ¬ λ°©μμ κ° μ μλ λ°©λ€μ stackμ λ£λλ€.
- μ°μ λ°©λ¬Έν΄μΌ νλ λ°©μ λ°©λ¬Ένμ§ μμ κ²½μ°, μ΄ν λ°©λ¬Έν΄μΌ νλ λ°©λ€μ μ μ₯νλ
- μ΄ν νμ¬ λ°© μ΄νμ λ°©λ¬Έν΄μΌ νλ λ°©(
after[now])μ stackμ λ£κ³ , λ°λ³΅νλ€.
π CODE
μ½λ 보기/μ κΈ°π«
import java.util.*;
class Solution {
boolean[] visited;
int[] before;
int[] after;
ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();
public boolean solution(int n, int[][] path, int[][] order) {
visited = new boolean[n];
before = new int[n];
after = new int[n];
// λ°©λ¬Έ μ°μ μμ μ μ₯
for (int[] or : order) before[or[1]] = or[0];
for (int i = 0; i < n; i++) adjList.add(new ArrayList<>());
// μΈμ 리μ€νΈ μμ±
for (int[] p : path) {
adjList.get(p[0]).add(p[1]);
adjList.get(p[1]).add(p[0]);
}
// 0λ³΄λ€ λ¨Όμ λ°©λ¬Έν΄μΌ νλ λ°©μ΄ μλ€λ©΄ λ°λ‘ false
if (before[0] != 0) return false;
dfs();
// λͺ¨λ λ°©λ¬Έ ν, λ°©λ¬Ένμ§ μμ λ°©μ΄ μλ€λ©΄ false
for (int i = 0; i < n; i++)
if (!visited[i]) return false;
return true;
}
private void dfs() {
Stack<Integer> stack = new Stack<>();
stack.push(0);
visited[0] = true;
for (int next : adjList.get(0)) stack.push(next);
while(!stack.empty()) {
int now = stack.pop();
if (visited[now]) continue;
if (!visited[before[now]]) {
after[before[now]] = now;
continue;
}
visited[now] = true;
for (int next : adjList.get(now))
if (!visited[next]) stack.push(next);
stack.push(after[now]);
}
}
}
βοΈ Review
- μμ μ λ ¬ μκ³ λ¦¬μ¦μ λ μ¬λ Έμλλ°, λ°©λ¬Ένλ λ°©λ λ€μ λ°©λ¬Έν΄μΌνλ κ²½μ°κ° μμ μ μμ΄, μλ―Έκ° μλ€κ³ νλ¨νλ€.
- μμλ λ§μ§λ§ λ¬Έμ λ΅κ², λμ΄λκ° λμλ€. μΈν΄ μ½ν 5μμ κ·Έλ¦Όμ λ‘μ΄λΌλ μκ°μ΄ λ€μλ€ ..